This invention relates generally to local area networks (LANs) of the Ethernet type and, more particularly, to techniques for improving fairness of channel access in an Ethernet LAN. Ethernet is a commonly used name for a LAN that uses a network access protocol referred to as Carrier Sense Multiple Access with Collision Detection (CSMA/CD). The CSMA/CD protocol is defined in ANSI/IEEE Std 802.3, published by the Institute of Electrical and Electronics Engineers, Inc., 345 East 45th Street, New York, N.Y. 10017, and referred to in this specification as "the IEEE 802.3 standard." The standard is for a 10 Mbps (megabits/sec) CSMA/CD channel, but it will be understood that the present invention may also be applicable to a 100 Mbps channel.
Under the CSMA/CD rules for access to a network bus or cable, which will be referred to as the channel, any node or station wishing to transmit must first "listen" to make sure that the channel is clear before beginning to transmit. All nodes on the network have equal priority of access and may begin transmitting as soon as the channel is clear and a required inter-packet delay of 9.6 .mu.s (microseconds) has elapsed. However, if a first node that has started transmitting detects a "collision" with a transmission from another node, the first node continues transmitting for a short time to make sure that all nodes wishing to transmit will detect the collision. Every other node detecting the collision also continues to transmit for a short time. Then each node that has detected a collision terminates transmission of the packet or frame. The nodes involved in the collision wait for the required interpacket delay of 9.6 .mu.s and then select random, and therefore usually different, delay times, referred to as backoff times, before trying transmission of the same packet again.
More specifically, the IEEE 802.3 standard defines a collision backoff procedure referred to as "truncated binary exponential backoff." When a transmission attempt has terminated due to a collision, it is retried by the transmitting node, after a selected backoff time, until either the transmission is successful or a maximum number of attempts have been made and all have terminated due to collisions. The backoff time is selected by each node as an integral multiple of the "slot time," which is the maximum round-trip propagation time for the network. i.e. the time to propagate a data packet from one end of the network to the other, and back. The slot time defined by the IEEE 802.3 standard is 51.2 .mu.s. The number of slot times selected as the backoff time before the nth retransmission is chosen as a randomly distributed integer r in the range: EQU 0.ltoreq.r&lt;2.sup.k, where k=min (n, 10).
Therefore, for the first attempted retransmission the backoff time is selected as 0 or 1 slot times, for the second attempted retransmission the backoff time is selected as 0, 1, 2 or 3 slot times, for the third attempted retransmission the backoff time is selected as 0, 1, 2, 3, 4, 5, 6 or 7 slot times, and so forth. The maximum backoff time, for the tenth attempted retransmission may be up to 2.sup.10 -1, or 1,023 slot times, i.e. up to 52.4 ms (milliseconds).
The IEEE 802.3 standard for CSMA/CD operation is designed to achieve optimal performance, in throughput, latency and fairness, when the number of nodes in the network is relatively large. When the number of active nodes, i.e. nodes having data packets to transmit, is small, e.g. two nodes, the IEEE 802.3 standard exhibits an undesirable effect referred to as the capture effect, in which one of the nodes may effectively capture the channel and transmit a succession of data packets in a back-to-back fashion for a relatively long period of time. The capture effect is best understood from a simple example.
Suppose there are two active nodes, A and B, in a network and they begin transmitting at approximately the same time, resulting in a first collision. They each select backoff times of 0 or 1 slot time, in accordance with the standard backoff algorithm. Suppose further that node A selects zero backoff time and node B selects one slot time as its backoff time. Obviously, node A will be able to successfully transmit on its first attempt at retransmission. Node B will wait a full slot time before making its first retransmission attempt, but by this time node A has started transmitting a second data packet, i.e. node A is transmitting successive packets back-to-back, with only the required interpacket gap (IPG) separating them. Node B experiences a second collision on its first data packet, but for node A it is still a "first" collision for trying to transmit a second data packet. In accordance with the standard backoff algorithm, node A selects a backoff of 0 or 1 slot time, but node B selects a backoff of 0, 1, 2 or 3 slot times. Therefore, node B has only one chance in eight of winning access to the channel (if node B chooses 0 and node A chooses 1). Node A, however, has five chances in eight of winning channel access. (Two of the eight possibilities will result in another collision.) Clearly, it is more probable, actually five times more probable, that node A will retain access to the channel, as compared with node B. If the probable occurs, and node A transmits its second data packet,the situation becomes progressively more difficult for node B to transmit. If another collision occurs on node B's next attempt to retransmit, this will be node B's third attempt, but node A's "first" again. Node A's backoff is still 0 or 1 slot time, but node B's is selected from 0 through 7 slot times. Node A is then thirteen times as likely to win access to the channel on the next attempted retransmission. For the nth attempt at retransmission by node B, node A will be (2.sup.n -3) times more likely to win access to the channel. For the maximum value of n, i.e. 10, the unfairness factor between the two active nodes will be 2.sup.10 -3, or 1,021.
For network protocols that require a receiving node to acknowledge that it has received a packet, the situation is further aggravated by the need to transmit acknowledgment messages on the network. For example node A captures the channel and is sending successive packets to node B, node B may be unable to acknowledge even the first received packet. Node A will eventually have to give up the channel to allow acknowledgements to flow back from node B, but this is an inefficient process and channel utilization goes down.
It is important to understand the effect of the interpacket gap (IPG) when one node has captured the channel. For example, consider the case in which two nodes (A and B) are contending for the channel before capture may be said to have occurred. (Again, nodes A and B are assumed to have messages to transmit, and to be the only active nodes on the network. ) After the first collision, node A selects a backoff time of zero time slots and node B a backoff time of one time slot. Therefore, node A waits just for the IPG interval of 9.6 .mu.s and begins transmitting its first packet again. When node A wins again on its second packet transmission, node A is considered to have captured the channel. Node B waits for its one time slot backoff interval, then checks to see if the channel is idle, but has to wait until node A finishes transmitting a second packet.
The standard rules with regard to IPG intervals are structured such that all nodes must wait for one IPG interval following first sensing channel inactivity at the end of a packet transmission. This applies to node A in the example, which has just finished transmitting a second packet, and to node B, which has sensed that another node has finished transmitting. As soon as the channel becomes idle, node A must observe a "transmit-to-transmit" IPG and node B must observe a "receive-to-transmit" IPG. Both IPG intervals are the same (9.6 .mu.s), so inevitably both nodes will again be contending equally for the channel at the end of the IPG. This equality of node status in the contention is designed to be fair in the situation when many nodes are competing for channel access, but contains an element of unfairness when one of two nodes has captured the channel. As both stations wait for identical intervals of time, the unfairness caused by the backoff algorithm is allowed to persist.
It will be appreciated from the foregoing that there is a need for improvement over the standard approach for selecting random backoff times in a network using the CSMA/CD protocol. Ideally, any improved technique should still comport with the objects of the IEEE 802.3 standard and should be compatible with nodes that use the standard without improvement. The present invention achieves these ends, as will become apparent from the following summary.